val input = TextIO.openIn("input.txt");

fun printInt (a:int) =
    print(Int.toString(a)^" ");

fun getInt () =
    Option.valOf (TextIO.scanStream (Int.scan StringCvt.DEC) input);
    
fun printIntList ( [] ) = ()
  | printIntList ( x::xs ) = 
    let
	val tmp = printInt(x)
    in
	printIntList(xs)
    end;

fun getIntList ( 0 ) = []
  | getIntList ( N:int) = getInt()::getIntList(N-1);

fun split [ ]  = ([ ], [ ]) 
    | split [x] = ([ ], [x])
    | split (x::y::L) =
	let val (A, B) =split L
	in (x::A, y::B) 	
	end;

datatype tree = Empty | Br of tree * int * tree; 

fun trav(Br(t1,a,t2)) = trav(t1)@(a::trav(t2))
    |trav empty = [];

(* 前序遍历 *)
fun trav1(Br(t1, a, t2)) = a::(trav1(t1)@trav1(t2))
    |trav1 empty = [];

fun listToTree ([] : int list) : tree = Empty
  | listToTree (x::l) = let val (l1, l2) = split l
    	in Br(listToTree l1, x, listToTree l2)
  end;


(*begin*)
fun treecompare(Br(_, a, _), Br(_, b, _)) = Int.compare(a, b);
fun SwapDown(Empty) = Empty
    | SwapDown(Br(t1, a, Empty)) = Br(t1, a, Empty)
    | SwapDown(Br(Empty, a, t1)) = Br(Empty, a, t1)
    | SwapDown(Br(Br(l1, cl, l2), r, Br(r1, cr, r2))) = if r > cr then Br(Br(l1, cl, l2), cr, SwapDown(Br(r1, r, r2))) else if r > cl then Br(SwapDown(Br(l1, r, l2)), cl, Br(r1, cr, r2)) else Br(Br(l1, cl, l2), r, Br(r1, cr, r2));

fun heapify(Empty) = Empty
    | heapify(Br(t1, r, t2)) = SwapDown(Br(heapify t1, r, heapify t2));

(*end*)

val L = getIntList(7);
printIntList (trav(heapify(listToTree L)));
printIntList (trav1(heapify(listToTree L)));